package com.xinheyun.demo.leetcode;

import java.util.Arrays;
import org.junit.Test;

/**
 * @description: TODO
 * @author: Sarah
 * @modified By: Sarah
 * @date: Created in 2021/8/31 15:44
 * @version:v1.0
 */

//输入：batchSize = 3, groups = [1,2,3,4,5,6]
//    输出：4
//    解释：你可以将这些批次的顾客顺序安排为 [6,2,4,5,1,3] 。那么第 1，2，4，6 组都会感到开心。
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/maximum-number-of-groups-getting-fresh-donuts
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//有一个甜甜圈商店，每批次都烤 batchSize 个甜甜圈。这个店铺有个规则，就是在烤一批新的甜甜圈时，之前 所有 甜甜圈都必须已经全部销售完毕。给你一个整数 batchSize 和一个整数数组 groups ，数组中的每个整数都代表一批前来购买甜甜圈的顾客，其中 groups[i] 表示这一批顾客的人数。每一位顾客都恰好只要一个甜甜圈。
//
//    当有一批顾客来到商店时，他们所有人都必须在下一批顾客来之前购买完甜甜圈。如果一批顾客中第一位顾客得到的甜甜圈不是上一组剩下的，那么这一组人都会很开心。
//
//    你可以随意安排每批顾客到来的顺序。请你返回在此前提下，最多 有多少组人会感到开心。
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/maximum-number-of-groups-getting-fresh-donuts
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
public class test1815 {

    @Test
    public void maxHappyGroups() {
        int[] groups = {1,2,3,4,5,6};
        int sum = Arrays.stream(groups).sum();
        int[] dp = new int[sum+1];
        dp[0]=1;
        for(int group : groups){
            for (int i = sum; i >=group ; i--) {
                dp[i]+=dp[i-group];

            }
        }
        System.out.println(dp);

    }

}
